#ifndef SKIPLIST_H
#define SKIPLIST_H
/**
 * \bibitem{pugh1990} 
 * W. Pugh, ``Skip lists: A probabilistic alternative to balanced trees,'' \textit{Communications of the ACM}, vol. 33(6), pp. 668--676, 1990.
 */

#include <cstdint>
#include <random>

namespace RealScan
{

// SkipList Node Type. 
template <typename T>
struct SkipNode
{
    std::int32_t key;
    T value;

    int level;

     // Multi-level forward pointers, the core of the SkipList
    SkipNode<T> **forward;  

    // Constructor with key
    explicit SkipNode(int l, std::int32_t _key) : key(_key), value(T()), level(l)
    {
        forward = new SkipNode<T>*[l];
        std::fill(forward, forward + l, nullptr);
    }

    // Constructor with key and value
    SkipNode(int l, std::int32_t _key, const T& _value) : key(_key), value(_value), level(l)
    {
        forward = new SkipNode<T>*[l];
        std::fill(forward, forward + l, nullptr);
    }

    // Destructor
    ~SkipNode() { delete[] forward; }
};

// SkipList. Recommended: L = log2(N), where N is the data size.
template <typename T, int L>
class SkipList
{
public:
    static_assert(L > 0);

    // Node type
    using Node = SkipNode<T>;

    // Constructor
    SkipList()
    {
        // Initialize random seed
        srand(static_cast<unsigned>(time(0)));

        // Initialize head and tail nodes
        m_head = new Node(L, INT32_MIN);
        m_tail = new Node(L, INT32_MAX);

        // Set up forward links
        for (int l = 0; l < L; ++l)
        {
            m_head->forward[l] = m_tail;
        }
    }

    // Destructor
    ~SkipList()
    {
        // Remove all nodes starting from level 0 (acts as a linked list)
        Node* node = m_head->forward[0];

        while (node != m_tail)
        {
            Node* temp = node;
            node = node->forward[0];
            delete temp;
        }

        // Delete head and tail nodes
        delete m_head;
        delete m_tail;
    }

    // Search for a node
    Node* search(std::int32_t search_key)
    {
        /*
         * Reference [1]: Figure 2. Skip List Search Algorithm
         */
        Node* x = m_head;

        for (int l = m_level - 1; l >= 0; --l)
        {
            while (x->forward[l]->key < search_key)
            {
                x = x->forward[l];
            }
        }
        x = x->forward[0];

        return (x->key == search_key) ? x : nullptr;
    }

    // Insert a node
    Node* insert(std::int32_t target_key, const T& new_value)
    {
        /*
         * Reference [1]: Figure 4. Skip List Insertion and Deletion Algorithms
         */
        Node* update[L] = {};
        Node* x = m_head;

        for (int l = m_level - 1; l >= 0; --l)
        {
            while (x->forward[l]->key < target_key)
            {
                x = x->forward[l];
            }
            update[l] = x;
        }
        x = x->forward[0];

        if (x->key == target_key)
        {
            x->value = new_value;
        }
        else
        {
            // Generate a random level for the new node
            int new_level = randomLevel();

            if (new_level > m_level)
            {
                for (int l = m_level; l < new_level; ++l)
                {
                    update[l] = m_head;
                }
                m_level = new_level; // Update the current level
            }

            // Create the new node
            x = new Node(new_level, target_key, new_value);

            m_size++; // Update node count

            for (int l = 0; l < new_level; ++l)
            {
                x->forward[l] = update[l]->forward[l];
                update[l]->forward[l] = x;
            }
        }
        return x;
    }

    // Remove a node
    void remove(int target_key)
    {
        /*
         * Reference [1]: Figure 4. Skip List Insertion and Deletion Algorithms
         */
        Node* update[L];
        Node* x = m_head;

        for (int l = m_level - 1; l >= 0; --l)
        {
            while (x->forward[l]->key < target_key)
            {
                x = x->forward[l];
            }
            update[l] = x;
        }
        x = x->forward[0];

        if (x->key == target_key)
        {
            for (int l = 0; l < m_level; ++l)
            {
                if (update[l]->forward[l] != x)
                    break;
                update[l]->forward[l] = x->forward[l];
            }
            delete x; // Delete the node
            m_size--; // Update node count

            // Adjust the current level
            while (m_level > 1 && m_head->forward[m_level - 1] == m_tail)
            {
                m_level--;
            }
        }
    }

    // Get the number of elements
    std::size_t size() const
    {
        return m_size;
    }

    // Get storage space (Byte)
    std::size_t space() const
    {
        std::size_t _space = 0;
        
        const Node* node = m_head->forward[0];
        while (node != m_tail)
        {
            _space += (sizeof(node->key) + sizeof(node->value) + sizeof(void*) * node->level);
            node = node->forward[0];
        }

        return _space;
    }

    // Get the head pointer
    const Node* head() const
    {
        return m_head;
    }

    // Get the tail pointer
    const Node* tail() const
    {
        return m_tail;
    }

    // Convert to a vector
    // Linked list --> Sorted vector, satisfying: minKey <= vec[i]->key <= maxKey
    void toVector(std::vector<Node*>& vec, std::int32_t minKey, std::int32_t maxKey)
    {
        // Clear the vector
        // vec.clear();

        // Invalid range check
        // if (xMin > xMax)
        //     return;

        // Locate the left boundary
        Node* x = m_head;
        for (int l = m_level - 1; l >= 0; --l)
        {
            while (x->forward[l]->key < minKey)
            {
                x = x->forward[l];
            }
        }
        x = x->forward[0];

        // Add nodes within the range
        while (x->key <= maxKey)
        {
            vec.push_back(x);
            x = x->forward[0];
        }
    }

private:
    // Head pointer
    Node* m_head = nullptr;
    // Tail pointer
    Node* m_tail = nullptr;

    // Current number of levels
    int m_level = 1;

    // Number of elements
    std::size_t m_size = 0;

    /*
     * Reference: Figure 5. Algorithm to Calculate a Random Level
     * P = 0.5
     */
    int randomLevel()
    {
        int new_level = 1;
        while (rand() % 2 == 0)
        {
            new_level++;
        }
        return (new_level < L) ? new_level : L;
    }
};

} /* RealScan */ 

#endif /* SKIPLIST_H */